1. Field of the Invention
The present invention generally relates to the field of telecommunications and telecommunications networks, and to security issues related to telecommunications networks. More specifically, the present invention relates to methods and systems for protecting hash tables from attacks.
2. Description of the Related Art
Hash tables are widely used as a means for storing data in several technological fields, and particularly in the fields of telecommunications and networking. The reason of the extensive use of hash tables resides in the fact that hash tables allow inserting new data items, deleting obsolete data items and finding data items very efficiently in terms of average time per operation.
A hash table is a data structure that associates “keys” with “values”: given a key (e.g. a person's name), it is possible to find the corresponding value (e.g. that person's telephone number). The hash table works by transforming the key using a hash function into a hash, a number that the hash table uses to locate the desired value.
In telecommunications applications, hash tables are used for creating fast accessible data bases, e.g. for storing billing information or customer line data. Typically, networking devices, like for example gateways, routers, firewalls, and the like, store data items, e.g. IP (Internet Protocol) addresses, TCP/IP (Transmission Control Protocol/Internet Protocol) sessions, IPsec security associations etc., in a properly indexed hash table.
The mapping of data items to entries of the hash table is performed by a hash function, which receives as an input the key of a data item (such as a session's socket), and outputs an entry number of an entry of the hash table to which that data item is mapped. If several items are mapped to the same hash table entry, a situation referred to as a “collision” takes place. Method for resolving collisions are used, e.g. storing all the data items that are mapped to a same hash table entry in a linked list (a technique referred to as “hash chaining”).
The distribution of data items within a hash table, controlled by the adopted hash function, is critical to the efficiency of the data structure. The more even the distribution, the more efficient the table.
As known in the art, telecommunications apparatuses may be subjected to malicious attacks. Among the various types of malicious attacks that are experienced in the telecommunications and networking environments, one of the most common and effective is referred to as “Denial of Service” (DoS). The purpose of this type of attack is to reduce the capacity of some entity (e.g., a device, a software application, a network etc.) to perform the intended functions. A typical example of DoA attack is an attack against an e-commerce site, in which the web servers of the site are flooded with many bogus requests, thus leaving no resources to process legitimate requests. A DoS attack can be perpetrated against any component of the system which is required for providing a service and which can be affected in some way by an attacker.
Using a constant hash function in a networking or telecommunications device is known to expose the device to DoS attacks. The reason for this vulnerability is that an attacker may succeed in discovering the hash function used to map data items to the hash table, and thus to control part of the indexing key of a data item. The attacker may then be able to dictate the hash table entry in which the data item is stored. For example, if the networking device is a TCP/IP server and the attacker has an appropriate client software, then the attacker can control the client's port in the TCP/IP traffic (packets) sent to the networking device. If the networking device wishes to store in a hash table data concerning sessions opened to it, then a natural indexing key may be formed by the quintuple <Server IP address, Client IP address, IP protocol, Server port, Client port> (or, possibly, the indexing key may be only <Client IP address>). If the client port is controlled by the client, and thus by the attacker, the attacker can set it and, consequently, he/she can possibly control the entry in which the data items are stored. The aim of the attacker is to cause as many items as possible to be stored in a single entry of the attacked device's hash table; for example, the attacker may set up a lot of sessions, all of which are mapped to the same entry of the hash table. If k items are stored in a single hash table entry, then, on average, finding a new item in that entry takes O(k) operations, instead of O(1) (wherein O(k) means that the number of necessary operations increases with the increase of k, whereas O(1) means a constant number of operations). Thus, the lookup process in the networking device for, e.g., determining to which session received packets belong, is significantly slowed down, with the consequence that the overall performance of the networking device is reduced, causing a DoS condition.
In J. L. Carter and M. N. Wegman, “Universal classes of hash functions”, Journal of Computer and System Sciences (JCSS), 18(2), pp. 143-154, April 1979, and subsequently in S. Crosby and D. Wallach, “Denial of service via algorithmic complexity attacks”, in USENIX Security, 2003, it has been proposed to use a randomly selected hash function, instead of a constant (deterministic) hash function. More specifically, it was proposed to choose a universal family of hash functions and to select the hash function at random from that family. The underlying idea is that an attacker who has no prior knowledge of the hash function used to map data items to hash table entries is unable to predict which data items are mapped to each entry in the hash table; thus, the attacker cannot intentionally cause a large number of data items to be inserted into a single table entry, and so the above attack is avoided.
In J. Black et al., “UMAC: Fast and Secure Message Authentication”, Advances in Cryptology—CRYPTO '99, Lecture Notes in Computer Science, vol. 1666. pp. 216-233, Springer, 1999, a message authentication algorithm is proposed that uses a new universal hash function family, referred to as “NH”.